The present invention relates to memory devices and, more particularly, to error correction in memory devices such as Flash memory devices with multilevel cell architecture.
Memory devices are useful for storing and retrieving data utilized by a wide variety of computing processes and systems. Storing data into a memory device is also described as writing to the device or programming the device. Storing data may involve an erase operation, in which memory locations of the device are first set to a uniform level or value before being set to a desired data value. Retrieving data from a memory device is also described as reading from the device. A memory device may be external to a host machine, such as a memory device that can be accessed by a computer via a data bus connection such as Universal Serial Bus (USB), or a memory device may be incorporated with a host or with a processor device, to provide an integrated device such as a camera, cellular telephone, computer, network storage appliance, communications equipment, system component, and the like.
During read/write or program/erase processes in such memory devices, errors can be introduced, so that data stored into or retrieved from the memory device does not have the intended value. Thus, correction schemes such as error-correcting codes (ECC) have been devised to recover the original information. Generally, an ECC is based upon the idea of adding redundancy to the information such that errors induced by some physical effects are corrected. Many memory devices tend to have symmetric errors, either in large or small magnitude. In fact, the most well-studied model for error correcting codes in an information channel is for errors in a symmetric channel. According to the symmetric channel model, a symbol taken from the code alphabet is changed by an error event to another symbol from the same alphabet, and all such transitions are equally probable. That is, an error event that results in a low symbol changing to a high symbol is as likely as an error event that results in a high symbol changing to a low symbol. The natural error model that corresponds to the symmetric channel is the model of symmetric errors, whereby the Hamming weight is used as a constraint on legal error vectors. The popularity of the symmetric channel model, and the corresponding Hamming error model, stem from their applicability to practical applications, but more so from the powerful construction techniques that have been found to address them. A wide variety of ECC have been developed to correct such symmetric channel errors and are commonly used for a wide range of memory devices.
Asymmetric errors can also be introduced in certain data devices. For example, Flash memory is a non-volatile memory (NVM) technology that is both electrically programmable and electrically erasable. This property, together with high storage densities and high speed programming, has made Flash memory one of the dominant non-volatile memory technologies for many portable applications. In Flash memories, asymmetric errors are caused by programming/erasing processes suited for such devices. This is especially the case with more recent multilevel Flash cell memories. A typical two-level Flash memory represents a single bit of information, set to a zero level or a high level to represent a binary zero or a binary one. Such Flash cells will be referred to as two-level Flash memory cells. A multilevel Flash memory cell utilizes multiple levels to represent multiple bits of information with just a single memory cell. For example, a multilevel cell might use eight levels between the zero level and the high level used by a single level Flash memory cell to represent three bits of information (from 000 to 001 to 010 and so forth to 111).
In conjunction with conventional error processing schemes, data is stored into memory after an encoding process that introduces redundancy for the sake of error correction and data recovery during the decoding process. During encoding, raw information is received from a user (i.e., input data) and is encoded into codewords using an alphabet that can represent all the possible input values. In the case of a multilevel Flash cell memory, the cell levels are represented by a symbol, and multiple cells may be grouped together to form a symbol vector that corresponds to a codeword of the alphabet. For example, an eight-level Flash cell memory might group five cells together for processing. In such a case, each cell produces a symbol (for example, a symbol in the integer set {0, 1, 2, . . . , 7}), such that five symbols together correspond to a codeword of the alphabet (for example, a codeword comprising a symbol vector equal to {35311} where the vector is comprised of symbols). It is the five-symbol codeword that will be subjected to error correction processing. Thus, the coding alphabet in the example is comprised of the integer set {0, 1, 2, . . . , 7}, which will be referred to as Q. In the example, codewords comprise five-tuples.
Multilevel Flash cell memories have smaller error margins than conventional two-level Flash cell memories. As a result, errors that have a low magnitude can be induced due to several physical effects such as charge loss during charge placement/removal processes, cross cell interference, device aging, and the like. Each of these low magnitude error sources induces a level shift in one dominant direction, thus comprising what is referred to herein as an asymmetric error information channel. In general, the asymmetric error is due in part to the property of the cell programming algorithm of iteratively approaching cell target levels from below, without overshoot. The conventional ECC schemes, however, do not account for such asymmetric errors and primarily utilize a binary code to handle tractable symmetric errors.
Thus, the relatively well-studied ECC techniques for use with symmetric channel errors have been unavailable or not useful for application to asymmetric error devices such as multilevel Flash cell memories. In addition, conventional ECC techniques do not take advantage of peculiarities of the limited magnitude, asymmetric error characteristics of devices such as multilevel Flash memories. Lastly, conventional ECC techniques can be relatively slow and inefficient for storing and retrieving data from devices such as multilevel Flash memories.
It should be apparent from the discussion above that there is a need for ECC schemes that can be applied to the limited magnitude asymmetric error information channel model and that can result in more efficient ways to achieve reliable storage as well as faster storage and retrieval. The present invention satisfies this need.